package com.github.hgkmail.hello.leetcode101.base;

//并查集->父坐标数组
//并查集class优化版实现：父坐标数组(一维)、树的大小、初始化、find root(路径压缩)、is connected、union(按大小合并 把小的挂在大的下面)（6点+2优化）
public class UnionFindEx {
    //父坐标数组(一维)
    public int[] parent;
    //树的大小
    public int[] size;
    //初始化
    public UnionFindEx(int len) {
        parent = new int[len];
        size = new int[len];
        for (int i = 0; i < len; i++) {
            parent[i]=i; //指向自己
            size[i]=1; //一开始都是1
        }
    }
    //迭代查找根坐标(推荐，够简洁)
    public int find(int i) {
        while (parent[i]!=i) {
            //路径压缩，把i挂到爷爷节点
            parent[i]=parent[parent[i]];
            i=parent[i];
        }
        return i;
    }
    //是否相连（根坐标是否相同）
    //可用于判断无向图是否有回路：将一条边加入UF前，判断2个节点是否相连，如果相连，那么加入这条边后必定成回路
    public boolean isConnected(int i, int j) {
        return find(i)==find(j);
    }
    //合并
    public void union(int i, int j) {
        int rootI=find(i);
        int rootJ=find(j);
        if (rootI==rootJ) {
            return;
        }
        //把小的挂在大的下面
        if (size[rootI]>=size[rootJ]) {
            parent[rootJ]=rootI;
            size[rootI]+=size[rootJ];
        } else {
            parent[rootI]=rootJ;
            size[rootJ]+=size[rootI];
        }
    }

    //测试
    public static void main(String[] args) {
        UnionFindEx uf = new UnionFindEx(5);
        uf.union(0,1); //分量1
        uf.union(2,3); //分量2
        System.out.println(uf.isConnected(0,2));
        uf.union(1,4);
        uf.union(3,4);
        System.out.println(uf.isConnected(0,2));
    }
}
